package com.kobe.game_80;

import java.util.ArrayList;
import java.util.List;

/**
 * 
 * Consider quadratic Diophantine equations of the form:
 * 
 * x^(2) – Dy^(2) = 1
 * 
 * For example, when D=13, the minimal solution in x is 649^(2) – 13×180^(2) =
 * 1.
 * 
 * It can be assumed that there are no solutions in positive integers when D is
 * square.
 * 
 * By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the
 * following:
 * 
 * 3^(2) – 2×2^(2) = 1 2^(2) – 3×1^(2) = 1 9^(2) – 5×4^(2) = 1 5^(2) – 6×2^(2) =
 * 1 8^(2) – 7×3^(2) = 1
 * 
 * Hence, by considering minimal solutions in x for D ≤ 7, the largest x is
 * obtained when D=5.
 * 
 * Find the value of D ≤ 1000 in minimal solutions of x for which the largest
 * value of x is obtained.
 * 
 */

public class Game66 {

    public static void main(String[] args) {
        long max = 0L;
        long temp = 0L;

        for (int d = 1000; d >= 2; d--) {
            System.out.println("D " + d);
            if (cantSqrt(d) && !calculatedBefore(d)) {
                temp = (long) calculateX(d);
                if (temp > max) {
                    max = temp;
                    System.out.println("Max " + max + " | D " + d);
                }
            }
        }
        System.out.println(max);

    }

    private static boolean cantSqrt(int d) {
        double sqrt = Math.sqrt(d);
        if (sqrt == (int) sqrt)
            return false;
        return true;
    }

    private static List<Integer> Ds = new ArrayList<Integer>(1000);

    private static boolean calculatedBefore(int d) {
        for (int temp : Ds) {
            if (temp % d == 0) {
                double rest = Math.sqrt(temp % d);
                if (rest == (int) rest) {
                    System.out.println("calculated D:" + d + " before: " + temp
                            + " rest:" + rest);
                    return true;
                }
            }
        }
        Ds.add(d);
        return false;
    }

    private static double calculateX(int d) {
        double y = 2D;
        double x;
        for (;; y++) {
            if (y % 100000000 == 0) {
                System.out.println("D " + d + " | y:" + y/100000000 + "Y");
            }
            x = Math.sqrt(1 + d * y * y);
            if (x == (long) x) {
                long x_ = (long) x;
                long y_ = (long) y;
                if (x_ * x_ - d * y_ * y_ == 1) {
                    return x;
                }
            }
        }

    }
}
